\section{Árvores de Dados}
\subsection{Introdução}
		\paragraph{}Muitas vezes um software se vê limitado pelo uso de estruturas de dados pouco versáteis e muitas vezes muito mais lentas do que o esperado. É realmente comum encontrar algoritmos que teriam seu desempenho consideravelmente aumentado com o uso de estruturas robustas e eficientes como as árvores de dados. Nessa monografia, serão abordados os conceitos de árvores (\textit{trees}), árvores binárias (\textit{binary trees}), árvores de prefixo (\textit{tries}), árvores quádruplas (que serão chamadas apenas de \textit{quadtrees}), árvores octuplas (tratadas apenas como \textit{octrees}) e as \textit{R-trees}.
		\paragraph{}As árvores de dados são estruturas de dados feitas a partir de ponteiros emulando assim o formato de uma árvore. Sua principal utilidade é a de criar listas de conteúdo hierárquico ou de facilitar e agilizar as buscas em uma determinada lista de dados, usando uma estrutura composta por elementos que serão detalhadamente tratados a seguir.
	\subsection{Nodos (Nodes)}
		\paragraph{}Os nodes são as estruturas principais de uma árvore. São eles os responsáveis pelo crescimento da mesma para baixo e eles devem possuir necessariamente um valor, uma condição ou uma outra estrutura de dados. Isso permite que o nodo possua de zero a vários nodos filho (ou \textbf{child nodes}) que como o nodo pai (ou \textbf{parent node}), poderá trazer de zero a um nodo filho e assim por diante, tecendo a estrutura da árvore. Alguns nodos possuem características únicas, que serão discutidas a seguir.
	\subsubsection{Nodos Raízes (Root Nodes)}
		\paragraph{}Os nodos raízes, ou root nodes, são os nós que não possuem nodos pai, ficando no topo de toda a árvore, mas isso não impede que ele esteja no topo de uma árvore iniciada dentro de outra árvore. Geralmente é por ele que as operações se iniciam e assim seguem até os últimos nodos, que trataremos mais a frente. Em alguns tipos de árvores, os nodos raízes possuem características especiais, mas não cabe discutí-las aqui.
	\subsubsection{Nodos Folhas (Leaf Nodes)}
		\paragraph{}São os nodos que finalizam a árvore, não possuindo assim, nenhum nodo filho. Existem situações onde a árvore é iniciada por eles para depois acabar nos nodos raízes.
	\subsubsection{Nodos Internos (Internal Nodes)}
		\paragraph{}Assim é chamado qualquer nodo da árvore que possua nodos filhos, ou seja, que não sejam os nodos folhas.
	\subsection{Sub-Árvores (Subtrees)}
		\paragraph{}Um grupo de nodos contidos em uma árvore, quando unidos podem ser chamado de sub-árvore da árvore principal. Qualquer nodo, quando unido com os nodos que estão ao seu redor podem ser chamados de sub-árvore.
	\subsection{Ordenação}
		\paragraph{}Tratando-se de uma estrutura de dados, as árvores podem ser apresentadas de maneira ordenada ou não. Uma árvore desordenada apenas segue as características estruturais de uma árvore, não mantendo exatamente relações entre os nodos. Já as árvores ordenadas são de fato as mais usadas, e seguem toda a estrutura e ligações lógicas das árvores. Estão nesta categoria todas as árvores que serão listadas aqui nesta monografia.
	\section{Árvores Binárias}
		\paragraph{}A definição mais clássica para uma árvore binária é a de que, ou ela não possui nenhum elemneto, ou então possui uma raiz, ligada a outras duas sub-árvores. Por se tratar de um conceito recursivo, boa parte de suas funções são realizadas de maneira recursiva.
	\subsection{Definindo um nó}
		\paragraph{}Usa-se na definição de nó a declaração de um novo tipo de estrutura que segue a seguinte estrutura algorítmica:\\
		\\
\textit{declaração de tipo}\\
\tab \tab \textit{ PONTEIRO :  } \verb+^+ \textit{NO}\\
\tab\tab \textit{ NO \tab\tab :  resgitro}\\
\tab\tab\tab\tab\tab\tab \textit{ CONTEUDO : inteiro}\\
\tab\tab\tab\tab\tab\tab \textit{ DIR, ESQ : ponteiro}\\
\textit{\tab\tab\tab\tab\tab fim}\\
		\paragraph{}É fácil interpretar esse trecho de algoritmo: Primeiramente, é declarado um tipo de ponteiro que aponta para um nó, que é um registro declarado em seguida. Dentro do tipo nó, existe o seu conteúdo e pelo menos dois ponteiros que apontam para os nós filhos. Assim é selado o formato da árvore. Observe que em alguns tipos de de árvores, como as quadtrees e octrees, que possuem mais do que dois ponteiros declarados no registro do nó, apontando assim para mais de dois nós filhos.
	\subsection{Pesquisando um Nó}
		\paragraph{}De fato, uma das maiores vantagens em se usar uma árvore é a sua eficiência para pesquisa, que passa apenas por parte dos dados em busca do resultado. Para realizar uma pesquisa deste tipo, basta usar um algoritmo que realize os seguintes passos:\\
		\begin{itemize}
			\item Cheque se a árvore possui elementos;
			\item Cheque se o nó da raiz possui o dado procurado;
			\item Realize a busca na árvore caso as condições acima sejam falsas;
			\item Retorne a posição do nó desejado em um ponteiro.
		\end{itemize}
		\paragraph{}Um algoritmo desse tipo pode ser feito recursivamente, o que deixa o código ainda mais robusto. Um exemplo de como pode ser feita a busca é citado abaixo:\\
		\\
\textit{programa EXEMPLO}\\

\textit{		declaração de tipo\\}
\textit{		\tab\tab PONTEIRO :  } \verb+^+ \textit{ NO}\\
\textit{		\tab\tab NO \tab\tab :  resgitro}\\
\textit{		\tab\tab\tab\tab\tab\tab CONTEUDO : inteiro}\\
\textit{		\tab\tab\tab\tab\tab\tab DIR, ESQ : ponteiro}\\
\textit{		\tab\tab\tab\tab\tab fim}\\
\textit{		declaração de variáveis}\\
		\{...\}\\
\textit{		função PESQUISA(RAIZ : PONTEIRO; DADO : byte)} : PONTEIRO;\\
\textit{		inicio}\\
\textit{		\tab se RAIZ = nulo \{Verifica se existe o nó raiz\}}\\
\textit{		\tab\tab então PESQUISA  $\leftarrow$ nulo}\\
\textit{		\tab senão inicio}\\
\textit{		\tab\tab\tab se RAIZ} \verb+^+ \textit{ .CONTEUDO = DADO} \{Verifica se o nó raiz é o procurado\}\\
\textit{		\tab\tab\tab então PESQUISE $\leftarrow$  RAIZ}\\
\textit{		\tab\tab\tab senão inicio}\\
\textit{		\tab\tab\tab\tab\tab se RAIZ} \verb+^+ \textit{ .CONTEUDO<DADO} \{Direciona a pesquisa pela árvore\}\\
\textit{		\tab\tab\tab\tab\tab\tab então PESQUISA  $\leftarrow$  PESQUISA(RAIZ} \verb+^+ \textit{ .DIR, DADO)}\\
\textit{		\tab\tab\tab\tab\tab senão}\\
\textit{		\tab\tab\tab\tab\tab\tab PESQUISA  $\leftarrow$  PESQUISA(RAIZ} \verb+^+ \textit{ .ESQ, DADO)}\\
\textit{		\tab\tab\tab\tab  fim}\\
\textit{		\tab\tab  fim}\\
\textit{		fim}\\
		
\textit{		inicio do programa principal}\\
\textit{		\{...\}}\\
	\paragraph{}Tratando-se de uma função recursiva, vale lembrar sempre de ponderar se a recursividade no caso é vantajosa ou não e se esta não irá usar recursos inexistentes da máquina a ser utilizada.
	\subsection{Incluindo um nó}
		\paragraph{}Outra operação fundamental a ser feita com uma árvore é a inclusão de novos nós. É essa uma das grandes vantagens da árvore, que por ser dinâmica, pode alocar tantos novos nós quanto for possível armazenar na memória, sem sacrificar muito o desempenho da pesquisa, como é o caso de uma lista ou pilha.
		\paragraph{}Antes de fazer uma inclusão, é necessário fazer uma pesquisa para que não haja uma entrada duplicada, o que também garante que as pesquisas futuras retornem resultados eficientemente. Uma das formas de se fazer uma inclusão é mostrada nesse exemplo recursivo: \\
		\\
\textit{programa EXEMPLO}\\
\textit{		declaração de tipo}\\
\textit{		\tab\tab PONTEIRO :  } \verb+^+ \textit{ NO}\\
\textit{		\tab\tab NO \tab\tab :  resgitro}\\
\textit{		\tab\tab\tab\tab\tab\tab CONTEUDO : inteiro}\\
\textit{		\tab\tab\tab\tab\tab\tab DIR, ESQ : ponteiro}\\
\textit{		\tab\tab\tab\tab\tab fim}\\
\textit{		declaração de variáveis}\\
\textit{		\{ ... \} }\\

\textit{		procedimento INCLUSAO(DADO : inteiro ; RAIZ : PONTEIRO)}\\
\textit{		parâmetro de entrada: DADO : inteiro}\\
\textit{		parâmetro de saída:	  RAIZ : PONTEIRO}\\
\textit{		inicio}\\
\textit{		\tab se RAIZ=nulo}\\
\textit{		\tab\tab então inicio}\\
\textit{		\tab\tab\tab\tab novo vetor(RAIZ)}\\
\textit{		\tab\tab\tab\tab RAIZ} \verb+^+ \textit{ .CONTEUDO  $\leftarrow$  DADO}\\
\textit{		\tab\tab\tab\tab RAIZ} \verb+^+ \textit{ .DIR  $\leftarrow$  nulo}\\
\textit{		\tab\tab\tab\tab RAIZ} \verb+^+ \textit{ .ESQ  $\leftarrow$  nulo}\\
\textit{		\tab\tab\tab  fim}\\
\textit{		\tab senão inicio}\\
\textit{		\tab\tab\tab se DADO<RAIZ} \verb+^+ \textit{ .CONTEUDO então}\\
\textit{		\tab\tab\tab\tab INCLUSAO(RAIZ} \verb+^+ \textit{ .ESQ,DADOAUX)}\\
\textit{		\tab\tab\tab senão}\\
\textit{		\tab\tab\tab\tab INCLUSAO(RAIZ} \verb+^+ \textit{ .DIR,DADO)}\\
\textit{		\tab\tab  fim}\\
\textit{		fim}\\

\textit{		inicio do programa principal}\\
\textit{		\{...\}}
		\paragraph{}Nesse caso, o algoritmo primeiro confere se a árvore possui uma raiz e nas recursões, ela confere se existem dados alocados no local analizado. Caso seja verdadeiro, um novo ponteiro é criado e o dado é adcionado. No caso de já existir algo armazenado no local, o algoritmo chama recursivamente uma inclusão que fará as mesmas verificações no nó filho daquele primeiramente analizado. Assim se sucederá até que seja finalmente encontrado um nó que está realmente vazio.

	\subsection{Excluindo um nó}
		\paragraph{}Tão importante quanto incluir um nó é removê-lo, o que não é problema na árvore, já que todos os dados são adcionados de maneira ordenada e assim, por mais que se exclua um dos nós, a ordenação continua válida. Dessa maneira, existem fatores importantes que o algoritmo deve ponderar, como por exemplo, a existência de um dos nós filhos do nó a ser excluido ou até de mais do que um nó filho. Para que essa operação seja feita, é necessário usar dois procedimentos em recursividade. O primeiro é o encarregado pela substituição de um ponteiro por outro e o segundo é, de fato, a exclusão do nó:
\textit{programa EXEMPLO\\}
\textit{		declaração de tipo}\\
		\tab \tab \textit{ PONTEIRO :  } \verb+^+ \textit{ NO}\\
		\tab \tab \textit{ NO \tab\tab :  registro}\\
		\tab \tab \tab \tab \tab \tab \textit{ CONTEUDO : inteiro}\\
		\tab \tab \tab \tab \tab \tab \textit{ DIR, ESQ : ponteiro}\\
		\tab \tab \tab \tab \tab \textit{ fim}\\
\textit{		declaração de variáveis}\\
\textit{		\{...\}}\\
\textit{		procedimento SUBSTITUIR(ATUAL : PONTEIRO; NOVO : PONTEIRO)} \\
\textit{		parâmetro de entrada: NOVO:PONTEIRO}\\
\textit{		parâmetro de saída: ATUAL:PONTEIRO}\\
\textit{		declaração de variaveis internas}\\
\textit{		\tab PONTAUX : PONTEIRO}\\
\textit{		inicio}\\
\textit{		\tab se NOVO} \verb+^+ \textit{ .ESQ = nulo}\\
\textit{		\tab\tab então inicio}\\
\textit{		\tab\tab\tab\tab ATUAL} \verb+^+ \textit{ .CONTEUDO  $\leftarrow$  NOVO} \verb+^+ \textit{ .DADO}\\
\textit{		\tab\tab\tab\tab PONTAUX  $\leftarrow$  NOVO}\\
\textit{		\tab\tab\tab\tab NOVO  $\leftarrow$  NOVO} \verb+^+ \textit{ .DIR}\\
\textit{		\tab\tab\tab\tab deletar ponteiro (PONTAUX)}\\
\textit{		\tab\tab\tab  fim}\\
\textit{		\tab se não}\\
\textit{		\tab\tab\tab SUBISTITUIR(ATUAL,NOVO.ESQ)}\\
\textit{		fim}\\
\textit{		procedimento REMOVER(RAIZ : PONTEIRO ; DADO : inteiro)};\\
\textit{		parãmetro de entrada: RAIZ:PONTEIRO}\\
\textit{		parãmetro de saída: CONTEUDO:inteiro}\\
\textit{		declaração de variáveis internas:}\\
\textit{		\tab PONTAUX : PONTEIRO}\\
\textit{		inicio}\\
\textit{		\tab se raiz <> nulo}\\
\textit{		\tab\tab então inicio}\\
\textit{		\tab\tab\tab\tab se RAIZ} \verb+^+ \textit{ .CONTEUDO = nulo}\\
\textit{		\tab\tab\tab\tab então inicio}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab se RAIZ} \verb+^+ \textit{ .ESQ = nulo}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab\tab então inicio}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab\tab\tab\tab PONTAUX  $\leftarrow$  RAIZ}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab\tab\tab\tab RAIZ  $\leftarrow$  RAIZ} \verb+^+ \textit{ .DIR}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab\tab\tab\tab deletar ponteiro} \textit{(POINTAUX)}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab\tab\tab  fim}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab senão inicio}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab\tab\tab se RAIZ} \verb+^+ \textit{ .DIR = nulo}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab\tab\tab\tab então inicio}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab\tab\tab\tab\tab\tab PONTAUX  $\leftarrow$  RAIZ}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab\tab\tab\tab\tab\tab RAIZ  $\leftarrow$  RAIZ} \verb+^+ \textit{ .ESQ}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab\tab\tab\tab\tab\tab deletar ponteiro} \textit{(PONTAUX)}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab\tab\tab\tab\tab   fim}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab\tab\tab senão}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab\tab\tab SUBSTITUIR(RAIZ,RAIZ} \verb+^+ \textit{ .DIR)}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab\tab   fim}\\
\textit{		\tab\tab\tab\tab\tab\tab  fim}\\
\textit{		\tab\tab\tab\tab\tab senão}\\
\textit{		\tab\tab\tab\tab\tab\tab se RAIZ} \verb+^+ \textit{ .DADO < DADO}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab então REMOVER(RAIZ} \verb+^+ \textit{ .DIR,DADO)}\\
\textit{		\tab\tab\tab\tab\tab\tab\tab senão REMOVER(RAIZ} \verb+^+ \textit{ .ESQ,DADO)}\\
\textit{		\tab\tab\tab  fim}\\
\textit{		fim\\}
\textit{		inicio do programa principal\\}
\textit{		\{...\}\\}
		\paragraph{}Como é possível observar, este algoritmo seria bem mais trabalhoso se fosse feito sem utilizar a recursividade. Ele segue a seguinte linha de funcionamento: O primeiro procedimento substitui um nó por outro já existente e será chamado durante o procedimento de exclusão. Na exclusão, o algoritmo checa se esta é possível e chama recursivamente o procedimento de substituição.
	\section{Tries}
		\subsection{Visão Geral}
		\paragraph{}A origem da palavra tri vem do inglês re\textbf{trie}val, (recuperação) porque essa estrutura é basicamente usada na recuperação de dados. As tries podem realizar uma pesquisa em uma grande quantidade de texto. Suas chaves são formadas por uma combinação de símbolos do alfabeto, o que permite que as chaves sejam palavras. Sua estrutura fica explícita olhando a figura abaixo:\\
\\ 
		\includegraphics[bb=0 0 250 250]{tries.png}
\\

		\subsection{Aplicações e Vantagens}
		\paragraph{}Suas principais vantagens são a de baixo consumo de memória quando contêm um grande número de pequenas strings e também tornam fáceis e eficientes a busca nessas strings. Como aplicações, podemos ressaltar uma das mais comuns, que é a de dicionários e aplicações que exigem uma estrutura de dados ordenada e de busca eficiente.
		\subsection{Exemplo de Algoritmo de Pesquisa}
		\paragraph{}No algoritmo abaixo, temos uma função que verifica a existência de determinada string na trie.

	\section{Quadtrees}
		\subsection{Visão Geral}
		\paragraph{}A quadtree é uma árvore onde cada um dos nós possui até 4 nós filhos. A quadtree é mais comumente usada para armazenar a divisão recursiva de um espaço, que poderá ser divididos em quatro quadrantes que poderáo ser divididos novamente em mais 4 quadrantes e assim em diante. Para exemplificar o conceito, tomemos esse espaço 2D a ser dividido como sendo uma imagem. Temos então que a raiz é a representação da imagem e cada um dos 4 nós filhos seriam a representação dos subsequentes quadrantes em que a imagem foi dividida.
		\subsection{Vantagens e Desvantagens}
		\paragraph{}Tratando-se do seu uso em imagens, a sua principal vantagem é a de armazenar a imagem de forma mais compacta, além de existir uma maior facilidade em rotacionar as imagens para 90 graus, além de possuir uma forma mais compacta e robusta do que a árvore binária. A quadtree também possui visíveis desvantagens, tratando-se da criação de árvores a partir de imagens complexas e com várias cores.
		\subsection{Declarando uma Quadtree}
		\paragraph{}Os algoritmos de manipulação de uma quadtree são mais complexos do que o da árvore binária, já que deve ser criado visando uma função especifica. Segue-se o algoritmo de declaração do tipo "quadtree" que pode ser usado em todos os casos:\\
		\\
    		\textit{	Tipo}
		\textit{	\tab QUADTREE : Registro}\\
		\textit{	\tab\tab Cor : String; {Cria o fator a ser analizado da figura}}\\
		\textit{	\tab\tab NO, NE, SO, SE: PTRQUADTREES; {Cria os quadrantes}}\\
		\textit{	\tab Fim Registro}\\
		
		\textit{	\tab PTRQUADTREES : Ponteiro de QUADTREES;}

	\section{Octree}
		\subsection{Visão Geral}
		\paragraph{}Se a quadtree trata da divisão de um espaço 2D em quadrantes, a octree trata da divisão de espaços 3D em 4 quadrantes. Estruturalmente, trata-se de uma árvore na qual os nodos possuem até oito nós filhos que são a representação de um cubo em ambiente 3D e carregam informações que vão de vetores de estado até volume. As aplicações geralmente estão ligadas a divisão do espaço 3D para facilitar buscas com diversos objetivos.
		\paragraph{}Sua implementação é ainda mais especifica, e definitivamente não vem ao caso citá-la aqui, já que a principal intenção desta monografia é apresentar ao leitor as estruturas de dados mais comumente usadas para otimizar algoritmos e seus códigos, mas a sua declaração segue a linha de declaração das outras estruturas aqui citadas, alterando apena a adição de mais quatro nós filhos e raiz ou nó interno, como se vê no seguinte algoritmo:
		\\
    		\textit{Tipo\\
		\textit{	\tab OCTREES : Registro}\\
		\textit{	\tab\tab Cor : String; {Cria o fator a ser analizado da figura}}\\
		\textit{	\tab\tab NO, NE, SO, SE, NO2, NE2, SO2, SE2: PTRQUADTREES; {Cria os quadrantes}}\\
		\textit{	\tab Fim Registro}}\\
		
	\textit{		\tab PTROCTREES : Ponteiro de OCTREES;}

	\section{R-Trees}
		\subsection{Visão Geral}
		\paragraph{}A R-tree é um tipo de estrutura que se baseia no acesso espacial a informação, armazenando por exemplo, informações sobre a variável X e a variável Y de um determinado espaço. Cada um de seus nós armazena a posição do nó filho e o limite de todas as entradas desse nodo filho.
		\paragraph{}Para inserir ou exluir nós, são usadas caixas que limitam os nós e asseguram que os próximos nós estejam colocados no mesmo nó da folha. Cada  nó da folha armazena duas partes de informação: uma maneira de identificar o elemento de dados real, e outra caixa que limitando do elemento de dados.
		\paragraph{}Sua eficiência não é comprovadamente a melhor, mas é muito boa tratando-se do mundo real, o que se torna uma grande verdade. 
		\paragraph{}Por se tratar de uma estrutura ainda mais complexa, apenas serão indicados na bibliografia os sites que possuam seus metodos de implementação.

